package com.jiang.专题.动态规划.Q188;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/03 23:04
 */
class Solution {
    // 二维动态规划
//    public int maxProfit(int k, int[] prices) {
//        int len = prices.length;
//        int[][] dp = new int[len][k * 2];
//        for (int i = 0; i < k; i++) {
//            dp[0][i] = -prices[0]; // 持有股票，且没进行交易、进行一次交易、进行两次交易……进行k - 1次交易的最大利润
//            dp[0][i + k] = 0; // 不持有股票，且进行一次交易、进行两次交易……进行k次交易的最大利润
//        }
//        for (int i = 1; i < len; i++) {
//            for (int j = 0; j < k; j++) {
//                if (j == 0) {
//                    dp[i][j] = Math.max(dp[i - 1][j], -prices[i]);
//                } else {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j + k - 1] - prices[i]);
//                }
//                dp[i][j + k] = Math.max(dp[i - 1][j + k], dp[i - 1][j] + prices[i]);
//            }
//        }
//        return dp[len - 1][2 * k - 1];
//    }


    // 一维维动态规划
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int[] dp = new int[2 * k + 1]; // dp[1], dp[3]……dp[2 * k - 1]表示持有股票，且没进行交易、进行一次交易、进行两次交易……进行2 * k - 1次交易的最大利润； dp[2], dp[3],……dp[2 * k]表示不持有股票，且进行一次交易、进行两次交易……进行k次交易的最大利润

        // 初始化, 在prices[0]时，持有股票且进行0次交易，一次交易……2*k-1次交易的最大利润都为-prices[0]
        for (int j = 1; j < 2 * k; j += 2) {
            dp[j] = -prices[0];
        }

        for (int i = 0; i < len; i++) {
            for (int j = 1; j < 2 * k; j += 2) {
                dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + prices[i]);
            }
        }
        return dp[2 * k];
    }
}
